package leetcode.primary;

import java.util.ArrayList;
import java.util.List;

public class T68 {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> list = new ArrayList<>();
        int length = words.length;
        int start=0,end=0;
        int tempLen=0;
        int i=0;
        while (i<length){
            if (words[i].length()+tempLen+(end-start)<=maxWidth){
                tempLen+=words[i].length();
            }else {
                list.add(split(start,end,words,maxWidth,true));
                tempLen=words[i].length();
                start = end;
            }
            end++;
            i++;
        }
        list.add(split(start,end,words,maxWidth,false));
        return list;
    }

    public String  split(int start,int end,String[] words,int maxWidth,boolean fullJustify){
        StringBuilder temp = new StringBuilder();
        int wordsNum = end-start;
        if (wordsNum==1){
            temp.append(words[start]);
            temp.append(repeat(maxWidth-words[start].length()," "));
            return temp.toString();
        }
        int wordsLen = 0;
        for (int i=start;i<end;i++){
            wordsLen+=words[i].length();
        }
        int spaceNum = maxWidth-wordsLen;
        int averageNum = spaceNum/(wordsNum-1);
        int remain = spaceNum%(wordsNum-1);

        String space = repeat(averageNum, " ");
        if (fullJustify){
            int j=1;
            for (int i= start;i<end-1;i++){
                temp.append(words[i]);
                if (j<=remain){
                    temp.append(" ");
                    j++;
                }
                temp.append(space);
            }
            temp.append(words[end-1]);
        }else {
            for (int i = start; i < end; i++) {
                temp.append(words[i]);
                if(spaceNum!=0){
                    temp.append(" ");
                    spaceNum--;
                }
            }
            temp.append(repeat(spaceNum," "));
        }

        return temp.toString();
    }

    public  String repeat(int n,String str){
        if (n<=0){
            return "";
        }
        return String.valueOf(str).repeat(n);
    }

    public static void main(String[] args) {
        T68 test = new T68();
        String[] words = {"ask","not","what","your","country","can","do","for","you","ask","what","you","can","do","for","your","country"};


        List<String> list = test.fullJustify(words, 16);
        System.out.println("len="+list.size());
        for (String s : list) {
            for (int i=0;i<s.length();i++){
                if (s.charAt(i)==' '){
                    System.out.print("*");
                }else {
                    System.out.print(s.charAt(i));
                }
            }
            System.out.println();
        }
    }
}
